//1.和为k的子数组
//维护区间[0, i]的和
//要找所有和为k的子数组的个数, 只需要将以i位置为结尾的和为k的子数组个数累加即可
//以i位置为结尾的和为k的子数组个数: 本质是在求[x, i]和为k的个数
//也就是在求[0, x-1]的和为 sum - k的个数

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> mp;
        mp[0] = 1; //一定要有这句代码
        int sum = 0, cnt = 0;
        for(auto x : nums)
        {
            sum += x;
            if(mp.count(sum - k)) cnt += mp[sum - k];
            mp[sum]++;
        }
        return cnt;
    }
};

//2.和可被k整除的子数组
//同余定理: (a - b) % p == 0  <=>  a % p == b % p
class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        int n = nums.size(), sum = 0, ret = 0; 
        unordered_map<int, int> hash; //(前缀和 %k 的结果, 个数)
        hash[0 % k] = 1; 
        for(auto x : nums)
        {
            sum += x;
            int r = (sum % k + k) % k; //注意模加模补正
            if(hash.count(r)) ret += hash[r];
            hash[r]++;
        }
        return ret;
    }
};